1. Field
The present invention relates generally to decoding of variable-length prefix codes, e.g., Huffman codes, and, more specifically, to a new, combined decoding scheme of lookup table decoding and prefix oriented decoding.
2. Description
Entropy coding is a widely used data compression technique that many video and audio coding standards are based on. The theoretical basis of entropy coding states that a compression effect can be reached when the most frequently used data are coded with a fewer number of bits than the number of bits denoting the less frequently appearing data. This approach results in coded data streams composed of codes having different lengths.
There are a number of methods to form such variable length codes (VLC). One popular method uses a prefixed coding in which a code consists of a prefix that allows a decoding system to distinguish between different codes, and several significant bits representing a particular value (e.g., Huffman coding).
While most coding standards employ Huffman codes with prefixes composed of a series of ‘1’ or ‘0’ bits in their coding schemes, some standards (e.g., ISO/IEC 14496-2, Moving Pictures Experts Group (MPEG)-4 coding standard, Visual) allow for different coding schemes prefixed with a series of longer bit patterns.
As a general rule, the number of bits that comprise a variable length code depends on the number of bits that comprise the prefix of the code. At the same time, an experimentally defined subset of most frequently appearing codes may have relatively short prefixes (including zero prefix) and, thus, may be decoded in a lookup manner as a single code, which may be a faster way of decoding for a particular system.
Therefore, a need exists for the capability to provide high speed decoding of variable length codes prefixed with regular combinations of bits, in accordance with the actual frequency-to-code length distribution.